#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 2005;

void solve() {
  int s, k;
  cin >> s >> k;
  if (s % k == 0) {
    cout << k << endl;
    return;
  }
  if (s > k * k) {
    cout << max(1, k - 2) << endl;
    return;
  }
  vector<bool> f(s + 1, 0);
  f[0] = true;
  per(i, k, 1) {
    if ((k - i) % 2 == 0) {  // left to right
      per(j, s, 0) f[j] = j >= i && f[j - i];
      rep(j, i, s) f[j] = f[j] || f[j - i];
    } else {
      rep(j, 0, s) f[j] = j + i <= s && f[j + i];
      per(j, s - i, 0) f[j] = f[j] || f[j + i];
    }
    if (f[s]) {
      cout << i << endl;
      return;
    }
  }
  cout << 1 << endl;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}